{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import crcmod\n",
    "import struct\n",
    "import pandas as pd\n",
    "%matplotlib inline\n",
    "import matplotlib\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Flip a bit in a messsage\n",
    "def flip_bit(msg, idx):\n",
    "    bit_offset = idx % 8\n",
    "    byte_offset = idx / 8\n",
    "    mask = 0x1 << (7-bit_offset)\n",
    "    return msg[:byte_offset] + chr(ord(msg[byte_offset]) ^ mask) + msg[(byte_offset+1):]\n",
    "\n",
    "def xor_strings(s1,s2):\n",
    "    xored_bytes = [ord(a) ^ ord(b) for a,b in zip(s1,s2)]\n",
    "    return str(bytearray(xored_bytes))\n",
    "\n",
    "def bin_str(s, sep=\"\"):\n",
    "    return sep.join(format(ord(c), '08b') for c in s)\n",
    "\n",
    "def bin_short(short_val):\n",
    "    return bin_str(struct.pack('>H', short_val))\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 1f014829080a1d1802ad2800002bdfff83c5 xor \n",
    "# 1f014829100a1d1802ad2800002bdfff014b = \n",
    "# 00000000180000000000000000000000828e (B1 & C1)\n",
    "\n",
    "# 1f014829080a1d1802ad2800002bdfff83c5 xor\n",
    "# 1f0148291c0a1d1802ad2800002bdfff020a = \n",
    "# 0000000014000000000000000000000081cf (B2 & C2)\n",
    "\n",
    "# 1f02d5af180a1d1801d9180000102fff020a xor\n",
    "# 1f02d5af140a1d1801d9180000102fff014b = \n",
    "# 000000000c00000000000000000000000341\n",
    "\n",
    "# C2 = 0341\n",
    "# B1 xor B2 = 000000000c0000000000000000000000 0341\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Use single bit comparisons to RE a standard crc16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m1   11011110101011011011111011101111, crc = 0001010001011101\n",
      "m2   11010110101011011011111011101111, crc = 0101100111111110\n",
      "diff 00001000000000000000000000000000, crc = 0100110110100011\n",
      "                                xored crcs = 0100110110100011\n",
      "================================================================================\n",
      "m1   11011110101011011011111011101111, crc = 0001010001011101\n",
      "m2   11011010101011011011111011101111, crc = 1011000011101100\n",
      "diff 00000100000000000000000000000000, crc = 1010010010110001\n",
      "                                xored crcs = 1010010010110001\n",
      "================================================================================\n",
      "m1   11011110101011011011111011101111, crc = 0001010001011101\n",
      "m2   11011100101011011011111011101111, crc = 1100010001100101\n",
      "diff 00000010000000000000000000000000, crc = 1101000000111000\n",
      "                                xored crcs = 1101000000111000\n",
      "unshift_xor at 4 = 0000010011000001\n",
      "unshift_xor at 5 = 0000010011000001\n",
      "original poly    = 0000010011000001\n"
     ]
    }
   ],
   "source": [
    "\n",
    "poly = 0x104c1\n",
    "crc = crcmod.mkCrcFun(poly, initCrc=0, xorOut=0x0, rev=False)\n",
    "\n",
    "# Now consider two CRC values obtained from two 1-bit messages, \n",
    "# where the 1 bits are in adjacent positions. The resulting CRCs \n",
    "# will differ by just one shift-xor cycle. To be precise, if\n",
    "# C1 corresponds to the message with a 1 in position i, and\n",
    "# C2 corresponds to the message with a 1 in position i+1, then \n",
    "# C1 is derived from applying one shift-xor cycle to C2. \n",
    "# (If this seems backwards, it's because the further the 1 \n",
    "# bit is from the end of the message, the more shift-xor cycles\n",
    "# get applied to the CRC.)\n",
    "\n",
    "# The unshift_xor() function tries to reverse a shift-xor cycle\n",
    "\n",
    "def unshift_xor(a,b):\n",
    "    return ((b << 1) ^ a) & 0xffff\n",
    "\n",
    "def view_diff(msg, bit_to_flip):\n",
    "    m1 = msg.decode('hex')\n",
    "    m2 = flip_bit(m1,bit_to_flip)\n",
    "\n",
    "    diff = xor_strings(m1,m2)\n",
    "\n",
    "    print \"m1   %s, crc = %s\" % (bin_str(m1), bin_short(crc(m1)))\n",
    "    print \"m2   %s, crc = %s\" % (bin_str(m2), bin_short(crc(m2)))\n",
    "    print \"diff %s, crc = %s\" % (bin_str(diff), bin_short(crc(diff)))\n",
    "    crc_diff = crc(m1) ^ crc(m2)\n",
    "    print \"                                xored crcs = %s\" % bin_short(crc_diff)\n",
    "    return crc_diff\n",
    "\n",
    "msg = \"deadbeef\"\n",
    "crc_diff4 = view_diff(msg, 4)\n",
    "print \"=\" * 80\n",
    "crc_diff5 = view_diff(msg, 5)\n",
    "print \"=\" * 80\n",
    "crc_diff6 = view_diff(msg, 6)\n",
    "\n",
    "print \"unshift_xor at 4 = %s\" % bin_short(unshift_xor(crc_diff4, crc_diff5) & 0xffff)\n",
    "print \"unshift_xor at 5 = %s\" % bin_short(unshift_xor(crc_diff5, crc_diff6) & 0xffff)\n",
    "print \"original poly    = %s\" % bin_short(poly & 0xffff)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### crc diffs from observed omnipod single bit diff messages \n",
    "Indexed by position of bit diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The entry at crc_diff_dict[10][30] means we observed two 10 bytes messages that differed\n",
    "# only by a single bit, and the value at that entry is the xor of their crcs. \n",
    "crc_diff_dict = {\n",
    "    # Messages of length 10\n",
    "    10: {\n",
    "        30: 0b1000001010011011,\n",
    "        31: 0b1000000101010001,\n",
    "        34: 0b0000001110010010,\n",
    "        35: 0b1000001100101000,\n",
    "        36: 0b0000001100001110,\n",
    "        37: 0b1000000100001011,\n",
    "    },\n",
    "    \n",
    "    # Messages of length 3\n",
    "    3: {\n",
    "        30:  0b1000000100011111,\n",
    "        31:  0b0000001000111100,\n",
    "        34:  0b1000001011011100,\n",
    "        35:  0b0000000111010111,\n",
    "        36:  0b1000001101011001,\n",
    "        37:  0b1000000000011000,\n",
    "        38:  0b1000001010001110,\n",
    "        116: 0b0000000000101010,\n",
    "        117: 0b0000000011011010,\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Look at single bit diffs with unshift_xor()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "crc(30) = 1000000100011111\n",
      "crc(31) = 0000001000111100\n",
      "unshift_xor at 30 = 1000010101100111\n",
      "================================================================================\n",
      "crc(34) = 1000001011011100\n",
      "crc(35) = 0000000111010111\n",
      "unshift_xor at 34 = 1000000101110010\n",
      "================================================================================\n",
      "crc(35) = 0000000111010111\n",
      "crc(36) = 1000001101011001\n",
      "unshift_xor at 35 = 0000011101100101\n",
      "================================================================================\n",
      "crc(36) = 1000001101011001\n",
      "crc(37) = 1000000000011000\n",
      "unshift_xor at 36 = 1000001101101001\n",
      "================================================================================\n",
      "crc(37) = 1000000000011000\n",
      "crc(38) = 1000001010001110\n",
      "unshift_xor at 37 = 1000010100000100\n",
      "================================================================================\n",
      "crc(116) = 0000000000101010\n",
      "crc(117) = 0000000011011010\n",
      "unshift_xor at 116 = 0000000110011110\n",
      "================================================================================\n",
      "********************************************************************************\n",
      "crc(30) = 1000001010011011\n",
      "crc(31) = 1000000101010001\n",
      "unshift_xor at 30 = 1000000000111001\n",
      "================================================================================\n",
      "crc(34) = 0000001110010010\n",
      "crc(35) = 1000001100101000\n",
      "unshift_xor at 34 = 0000010111000010\n",
      "================================================================================\n",
      "crc(35) = 1000001100101000\n",
      "crc(36) = 0000001100001110\n",
      "unshift_xor at 35 = 1000010100110100\n",
      "================================================================================\n",
      "crc(36) = 0000001100001110\n",
      "crc(37) = 1000000100001011\n",
      "unshift_xor at 36 = 0000000100011000\n",
      "================================================================================\n"
     ]
    }
   ],
   "source": [
    "def crc_for(l,n):\n",
    "    crc = crc_diff_dict[l][n]\n",
    "    #crc = single_bit_crcs10[n]\n",
    "    \n",
    "    # collapse 5 bit 'hole'\n",
    "    #crc = (crc & 0b1111111111) + ((crc >> 5) & 0b10000000000)\n",
    "        \n",
    "    # Drop separate high bit\n",
    "    #crc = crc & 0b1111111111\n",
    "    \n",
    "    # Just look at lowest 8 bits\n",
    "    #crc = crc & 0b11111111\n",
    "    \n",
    "    return crc\n",
    "\n",
    "def diff_at(l,n):\n",
    "    return unshift_xor(crc_for(l,n), crc_for(l,n+1))\n",
    "\n",
    "def show_diff_at(l,n):\n",
    "    print \"crc(%d) = %s\" % (n, bin_short(crc_for(l,n)))\n",
    "    print \"crc(%d) = %s\" % (n+1, bin_short(crc_for(l,n+1)))\n",
    "    d = diff_at(l,n)\n",
    "    print \"unshift_xor at %d = %s\" % (n, bin_short(d))\n",
    "    print \"=\" * 80\n",
    "\n",
    "show_diff_at(3,30)\n",
    "show_diff_at(3,34)\n",
    "show_diff_at(3,35)\n",
    "show_diff_at(3,36)\n",
    "show_diff_at(3,37)\n",
    "show_diff_at(3,116)\n",
    "print \"*\" * 80\n",
    "show_diff_at(10,30)\n",
    "show_diff_at(10,34)\n",
    "show_diff_at(10,35)\n",
    "show_diff_at(10,36)\n",
    "\n",
    "#df = pd.DataFrame(map(lambda x: [x, diff_at(x)], [30, 34, 35, 36]), columns=['idx', 'crc'])\n",
    "#df.plot.scatter(x='idx', y='crc', marker='.')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
